package leetcode_ago.LinearList;
/**
 * 判断是否相交链表，返回相交链表的起始节点
 * 即JZ52：输入两个链表，找出它们的第一个公共节点
 * 保留链表原始结构：所以不能改了headAheadB
 */
/**
 * 判断是否相交链表，【给定两个链表头节点headA,headB】返回相交链表的起始节点[保留原始结构]
 * 思路：a链表不相交的部分长a，b链表不相交的部分长b，c是相交部分长度。保留原始结构，所以不能改了headAheadB
 * 若两个链表有焦点，两个链表同时向后遍历，若某个链表到达终点，让它从对方链表的表头出发，继续后移
 * 最后两个链表一定会在交点回合，如果没有交点，便是两个同时走到null
 */
public class Num160_FindIntersectNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1=headA;
        ListNode cur2=headB;
        while(cur1!=cur2){
            if(cur1!=null){
                cur1=cur1.next;
            }else{
                cur1=headB;
            }
            cur2=cur2==null?headA:cur2.next;
        }
        return cur1;//为空同时走到null，有交点同时走到焦点
    }
}
